/*
 * Partition data structure.
 * Copyright (C) 2006 Bob Zimmermann <rpz@cse.wustl.edu>
 *
 *  This file is a part of BAT.
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * partition.c
 *
 * Partition data structure.
 *
 * $Id: partition.c 1409 2006-09-20 20:30:33Z rpz $
 *
 */

#include "partition.h"
partition_ops_t *
partition_ops_new(partition_delete_op delete)
{
  partition_ops_t *po;
  po = malloc(sizeof(partition_ops_t));

  po->delete = delete;

  return po;
}

partition_ops_t *
partition_ops_copy(const partition_ops_t * po)
{
  partition_ops_t *copy;

  copy = malloc(sizeof(partition_ops_t));
  copy->delete = po->delete;

  return copy;
}

void
partition_ops_delete(partition_ops_t * po, int befrei)
{
  if (befrei)
    free(po);
}

void
_partition_node_delete(void *pn, int befrei)
{
  if (befrei)
    free(pn);
}

partition_t *
partition_new(int init_size, partition_ops_t * ops)
{
  partition_t *p;
  darray_ops_t *dao;
  partition_delete_op delete;

  p = malloc(sizeof(partition_t));

  dao = darray_ops_new(NULL, NULL, NULL, _partition_node_delete);
  p->nodes = darray_new(init_size, dao);
  if (ops != NULL)
    delete = ops->delete;
  else
    delete = NULL;
  dao = darray_ops_new(NULL, NULL, NULL, delete);
  p->data = darray_new(init_size, dao);

  return p;
}

partition_t *
partition_new_from_darray(darray_t * da)
{
  partition_t *p;
  partition_node_t *n;
  da_pos_t i, sz;

  p = malloc(sizeof(partition_t));
  sz = darray_size(da);
  p->nodes = darray_new(sz, NULL);
  p->data = darray_copy(da);

  for (i = 0; i < sz; i++) {
    n = malloc(sizeof(partition_node_t));
    n->parent = i;
    n->rank = 0;
    darray_add(p->nodes, n);
    /*
     * ((partition_node_t *) darray_get(p->nodes, i))->parent =
     * i;
     */
  }

  return p;
}

void
partition_delete(partition_t * p, int befrei)
{
  if (p->nodes != NULL)
    darray_delete(p->nodes, 1);
  if (p->data != NULL)
    darray_delete(p->data, 1);
  if (befrei)
    free(p);
}

void
partition_clear(partition_t *p, int befrei)
{
  if(p->nodes != NULL)
    darray_clear(p->nodes, 1);
  if(p->data != NULL)
    darray_clear(p->data, 1);
}

part_pos_t
partition_size(partition_t * p)
{
  return darray_size(p->data);
}

void
partition_add(partition_t * p, void *data)
{
  partition_node_t *n;

  n = malloc(sizeof(partition_node_t));
  n->rank = 0;
  n->parent = darray_size(p->nodes);

  darray_add(p->nodes, n);
  darray_add(p->data, data);
}

void
partition_set(partition_t *p, part_pos_t pos, void *data)
{
  darray_set(p->data, pos, data);
}

void *
partition_get(partition_t * p, part_pos_t i)
{
  return darray_get(p->data, i);
}

void **
partition_get_array(partition_t * p)
{
  return darray_get_array(p->data);
}

void
partition_link(partition_t * p, part_pos_t i, part_pos_t j)
{
  partition_node_t *ni, *nj, *tmp;

  ni = darray_get(p->nodes, i);
  nj = darray_get(p->nodes, j);

  if (ni->rank > nj->rank) {
    tmp = ni;
    ni = nj;
    nj = ni;
  }
  else if (ni->rank == nj->rank)
    nj->rank++;

  ni->parent = j;
}

part_pos_t
partition_find(partition_t * p, part_pos_t i)
{
  partition_node_t *ni;

  ni = darray_get(p->nodes, i);
  if (ni->parent != i)
    ni->parent = partition_find(p, ni->parent);

  return ni->parent;
}
